package com.ict.ycwl.pathcalculate.service.Impl;

import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
import com.ict.ycwl.pathcalculate.form.GetColourConvexHullFrom;
import com.ict.ycwl.pathcalculate.mapper.AccumulationMapper;
import com.ict.ycwl.pathcalculate.mapper.GroupMapper;
import com.ict.ycwl.pathcalculate.mapper.RouteMapper;
import com.ict.ycwl.pathcalculate.mapper.TransitDepotMapper;
import com.ict.ycwl.pathcalculate.pojo.*;
import com.ict.ycwl.pathcalculate.service.MapDisplayService;
import com.ict.ycwl.pathcalculate.utils.*;
import com.ict.ycwl.pathcalculate.vo.ConvexPointVO;
import lombok.RequiredArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.math3.ml.clustering.CentroidCluster;
import org.apache.commons.math3.ml.clustering.KMeansPlusPlusClusterer;
import org.apache.commons.math3.ml.distance.EuclideanDistance;
import org.apache.commons.math3.random.MersenneTwister;
import org.apache.commons.math3.random.RandomGenerator;
import org.springframework.stereotype.Service;

import java.util.*;
import java.util.stream.Collectors;

import static com.ict.ycwl.pathcalculate.utils.BoundaryPoint.getShaoguanBoundary;

/**
 * 地图路线显示处理类
 *
 * @author yuhuaame
 */
@Slf4j
@Service
@RequiredArgsConstructor
public class MapDisplayServiceImpl implements MapDisplayService {

    private final GroupMapper groupMapper;
    private final TransitDepotMapper transitDepotMapper;
    private final AccumulationMapper accumulationMapper;
    private final RouteMapper routeMapper;

//    @Override
//    public List<List<LngAndLat>> getSplitLines() {
//        List<Group> groups = groupMapper.getGroupsByLikeName();
//
//        if (groups.size() < 2) {
//            throw new IllegalArgumentException("班组数量不够，无法画出分割线！");
//        }
//
//        //头尾指针
//        int head = 0;
//        int tail = 1;
//
//        List<List<LngAndLat>> result = new ArrayList<>();
//
//        while (head < groups.size()) {
//            //获取两个班组
//            Group g1 = groups.get(head);
//            Group g2 = groups.get(tail);
//            //获取两个班组的中转站
//            QueryWrapper<TransitDepot> q1 = new QueryWrapper<>();
//            q1.eq("group_id", g1.getGroupId());
//            List<TransitDepot> d1 = transitDepotMapper.selectList(q1);
//            QueryWrapper<TransitDepot> q2 = new QueryWrapper<>();
//            q2.eq("group_id", g2.getGroupId());
//            List<TransitDepot> d2 = transitDepotMapper.selectList(q2);
//            //检查两个班组是否有中转站
//            if (d1.size() == 0) {
//                head = (head + 1) % groups.size();
//                tail = (tail + 1) % groups.size();
//                groups.remove(g1);
//                continue;
//            }
//            if (d2.size() == 0) {
//                tail = (tail + 1) % groups.size();
//                groups.remove(g2);
//                continue;
//            }
//            //获取两个班组的中转站的聚集区
//            List<Accumulation> a1 = new ArrayList<>();
//            for (TransitDepot d : d1) {
//                QueryWrapper<Accumulation> q3 = new QueryWrapper<>();
//                q3.eq("transit_depot_id", d.getTransitDepotId());
//                List<Accumulation> a = accumulationMapper.selectList(q3);
//                a1.addAll(a);
//            }
//            List<Accumulation> a2 = new ArrayList<>();
//            for (TransitDepot d : d2) {
//                QueryWrapper<Accumulation> q4 = new QueryWrapper<>();
//                q4.eq("transit_depot_id", d.getTransitDepotId());
//                List<Accumulation> a = accumulationMapper.selectList(q4);
//                a2.addAll(a);
//            }
//            //将a1和a2进行数据转化
//            ArrayList<DoublePoint> lngLatMatrix = new ArrayList<>();
//            for (Accumulation a : a1) {
//                lngLatMatrix.add(new DoublePoint(new double[]{a.getLongitude(), a.getLatitude()}));
//            }
//            for (Accumulation a : a2) {
//                lngLatMatrix.add(new DoublePoint(new double[]{a.getLongitude(), a.getLatitude()}));
//            }
//            //找出聚集区的中心点
//            List<CentroidCluster<DoublePoint>> centroidClusters = myKmeans(1, 30, 0, lngLatMatrix);
//            Clusterable c = centroidClusters.get(0).getCenter();
//            LngAndLat center = new LngAndLat(c.getPoint()[0], c.getPoint()[1]);
//
//            List<LngAndLat> l = new ArrayList<>();
//            l.add(center);
//            result.add(l);
//
//            //继续下两个班组
//            head++;
//            tail = (tail + 1) % groups.size();
//        }
//
//        //添加韶关市边界点
//        addBoundary(result);
//
//        //添加韶关市中心点
//        addCenter(result, SHAOGUAN_CENTER_POINT);
//
//        return result;
//    }

//    @Override
//    public List<List<LngAndLat>> getSplitLines() {
//        List<Group> groups = groupMapper.getGroupsByLikeName();
//
//        if (groups.size() < 2) {
//            throw new IllegalArgumentException("班组数量不够，无法画出分割线！");
//        }
//
//        //头尾指针
//        int head = 0;
//        int tail = 1;
//
//        List<List<LngAndLat>> result = new ArrayList<>();
//
//        while (head < groups.size()) {
//            //获取两个班组
//            Group g1 = groups.get(head);
//            Group g2 = groups.get(tail);
//            //获取两个班组的中转站
//            QueryWrapper<TransitDepot> q1 = new QueryWrapper<>();
//            q1.eq("group_id", g1.getGroupId());
//            List<TransitDepot> d1 = transitDepotMapper.selectList(q1);
//            QueryWrapper<TransitDepot> q2 = new QueryWrapper<>();
//            q2.eq("group_id", g2.getGroupId());
//            List<TransitDepot> d2 = transitDepotMapper.selectList(q2);
//            //检查两个班组是否有中转站
//            if (d1.size() == 0) {
//                head = (head + 1) % groups.size();
//                tail = (tail + 1) % groups.size();
//                groups.remove(g1);
//                continue;
//            }
//            if (d2.size() == 0) {
//                tail = (tail + 1) % groups.size();
//                groups.remove(g2);
//                continue;
//            }
//            //获取两个班组的中转站的聚集区
//            List<Accumulation> a1 = new ArrayList<>();
//            for (TransitDepot d : d1) {
//                QueryWrapper<Accumulation> q3 = new QueryWrapper<>();
//                q3.eq("transit_depot_id", d.getTransitDepotId());
//                List<Accumulation> a = accumulationMapper.selectList(q3);
//                a1.addAll(a);
//            }
//            List<Accumulation> a2 = new ArrayList<>();
//            for (TransitDepot d : d2) {
//                QueryWrapper<Accumulation> q4 = new QueryWrapper<>();
//                q4.eq("transit_depot_id", d.getTransitDepotId());
//                List<Accumulation> a = accumulationMapper.selectList(q4);
//                a2.addAll(a);
//            }
//            //将a1和a2进行格式转换
//            LngAndLat[] l1 = new LngAndLat[a1.size()];
//            for (int i = 0; i < a1.size(); i++) {
//                l1[i] = new LngAndLat(a1.get(i).getLongitude(), a1.get(i).getLatitude());
//            }
//            LngAndLat[] l2 = new LngAndLat[a2.size()];
//            for (int i = 0; i < a2.size(); i++) {
//                l2[i] = new LngAndLat(a2.get(i).getLongitude(), a2.get(i).getLatitude());
//            }
//            //获取l1和l2的凸包
//            List<LngAndLat> convexHull1 = ConvexHull.convexHull(l1);
//            List<LngAndLat> convexHull2 = ConvexHull.convexHull(l2);
//
//            //方便测试部分
//            double[][] c1 = new double[convexHull1.size()][];
//            for(int i = 0; i < convexHull1.size(); i++){
//                c1[i] = new double[]{convexHull1.get(i).getLongitude(), convexHull1.get(i).getLatitude()};
//            }
//            double[][] c2 = new double[convexHull2.size()][];
//            for(int i = 0; i < convexHull2.size(); i++){
//                c2[i] = new double[]{convexHull2.get(i).getLongitude(), convexHull2.get(i).getLatitude()};
//            }
//
//            //对凸包进行格式转换
//            LngAndLat[] newL1 = new LngAndLat[convexHull1.size()];
//            for (int i = 0; i < convexHull1.size(); i++) {
//                newL1[i] = convexHull1.get(i);
//            }
//            LngAndLat[] newL2 = new LngAndLat[convexHull2.size()];
//            for (int i = 0; i < convexHull2.size(); i++) {
//                newL2[i] = convexHull2.get(i);
//            }
//            //对凸包进行排序
//            LngAndLat[] ll1 = LngAndLat.sortPointsByLongitude(newL1);
//            LngAndLat[] ll2 = LngAndLat.sortPointsByLongitude(newL2);
//
//            //获取分割线
//            int i = 0;
//            int j = 0;
//            List<LngAndLat> list = new ArrayList<>();
//            while (i < ll1.length && j < ll2.length) {
//                LngAndLat left = ll1[i];
//                LngAndLat right = ll2[j];
//                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
//                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
//                LngAndLat middle = new LngAndLat(newLog, newLat);
//                list.add(middle);
//
//                i++;
//                j++;
//            }
//            //对分割线进行纬度的排序
//            LngAndLat[] lines = list.toArray(new LngAndLat[0]);
//            LngAndLat[] r = LngAndLat.sortPointsByLatitude(lines);
//            List<LngAndLat> resultLine = Arrays.stream(r).collect(Collectors.toList());
//            result.add(resultLine);
//            //继续下两个班组
//            head++;
//            tail = (tail + 1) % groups.size();
//        }
//
//        //添加韶关市中心点
//        addCenter(result, SHAOGUAN_CENTER_POINT);
//
//        return result;
//    }

//    @Override
//    public List<List<LngAndLat>> getSplitLines() {
//        List<Group> groups = groupMapper.getGroupsByLikeName();
//
//        if (groups.size() < 2) {
//            throw new IllegalArgumentException("班组数量不够，无法画出分割线！");
//        }
//        //计算班组的多边形，才能按顺序求分割线
//        ArrayList<GroupShapeLngAndLat> groupsArray = new ArrayList<>();
//        ArrayList<GroupShapeLngAndLat> groupsShape = new ArrayList<>();
//        for (Group g : groups) {
//            QueryWrapper<TransitDepot> q = new QueryWrapper<>();
//            q.eq("group_id", g.getGroupId());
//            List<TransitDepot> t = transitDepotMapper.selectList(q);
//            double newLog = 0;
//            double newLat = 0;
//            for (TransitDepot tt : t) {
//                newLog += Double.parseDouble(tt.getLongitude());
//                newLat += Double.parseDouble(tt.getLatitude());
//            }
//            newLog /= t.size();
//            newLat /= t.size();
//            groupsArray.add(new GroupShapeLngAndLat(new LngAndLat(newLog, newLat), g.getGroupId()));
//        }
//        groupsShape.add(groupsArray.get(0));
//        groupsArray.remove(0);
//        while (!groupsArray.isEmpty()) {
//            GroupShapeLngAndLat from = groupsShape.get(groupsShape.size() - 1);
//            double[] fromDoubles = {from.getLngAndLat().getLongitude(), from.getLngAndLat().getLatitude()};
//            GroupShapeLngAndLat to = null;
//            double min = Double.MAX_VALUE;
//            for (GroupShapeLngAndLat gs : groupsArray) {
//                double[] toDoubles = new double[]{gs.getLngAndLat().getLongitude(), gs.getLngAndLat().getLatitude()};
//                double v = calculateEuclideanDistance(fromDoubles, toDoubles);
//                if (v < min) {
//                    min = v;
//                    to = gs;
//                }
//            }
//            groupsShape.add(to);
//            groupsArray.remove(to);
//        }
//
//        //头尾指针
//        int head = 0;
//        int tail = 1;
//
//        List<List<LngAndLat>> result = new ArrayList<>();
//
//        while (head < groupsShape.size()) {
//            //获取两个班组
//            GroupShapeLngAndLat gs1 = groupsShape.get(head);
//            QueryWrapper<Group> gq1 = new QueryWrapper<>();
//            gq1.eq("group_id",gs1.getGroupId());
//            Group g1 = groupMapper.selectOne(gq1);
//
//            GroupShapeLngAndLat gs2 = groupsShape.get(tail);
//            QueryWrapper<Group> gq2 = new QueryWrapper<>();
//            gq2.eq("group_id",gs2.getGroupId());
//            Group g2 = groupMapper.selectOne(gq2);
//
//            //获取两个班组的中转站
//            QueryWrapper<TransitDepot> q1 = new QueryWrapper<>();
//            q1.eq("group_id", g1.getGroupId());
//            List<TransitDepot> d1 = transitDepotMapper.selectList(q1);
//            QueryWrapper<TransitDepot> q2 = new QueryWrapper<>();
//            q2.eq("group_id", g2.getGroupId());
//            List<TransitDepot> d2 = transitDepotMapper.selectList(q2);
//            //检查两个班组是否有中转站
//            if (d1.size() == 0) {
//                head = (head + 1) % groups.size();
//                tail = (tail + 1) % groups.size();
//                groups.remove(g1);
//                continue;
//            }
//            if (d2.size() == 0) {
//                tail = (tail + 1) % groups.size();
//                groups.remove(g2);
//                continue;
//            }
//            //获取两个班组的中转站的聚集区
//            List<Accumulation> a1 = new ArrayList<>();
//            for (TransitDepot d : d1) {
//                QueryWrapper<Accumulation> q3 = new QueryWrapper<>();
//                q3.eq("transit_depot_id", d.getTransitDepotId());
//                List<Accumulation> a = accumulationMapper.selectList(q3);
//                a1.addAll(a);
//            }
//            List<Accumulation> a2 = new ArrayList<>();
//            for (TransitDepot d : d2) {
//                QueryWrapper<Accumulation> q4 = new QueryWrapper<>();
//                q4.eq("transit_depot_id", d.getTransitDepotId());
//                List<Accumulation> a = accumulationMapper.selectList(q4);
//                a2.addAll(a);
//            }
//            //将a1和a2进行格式转换
//            LngAndLat[] l1 = new LngAndLat[a1.size()];
//            for (int i = 0; i < a1.size(); i++) {
//                l1[i] = new LngAndLat(a1.get(i).getLongitude(), a1.get(i).getLatitude());
//            }
//            LngAndLat[] l2 = new LngAndLat[a2.size()];
//            for (int i = 0; i < a2.size(); i++) {
//                l2[i] = new LngAndLat(a2.get(i).getLongitude(), a2.get(i).getLatitude());
//            }
//            //获取l1和l2的凸包
//            List<LngAndLat> convexHull1 = ConvexHull.convexHull(l1);
//            List<LngAndLat> convexHull2 = ConvexHull.convexHull(l2);
//
//            //方便测试部分
//            double[][] c1 = new double[convexHull1.size()][];
//            for (int i = 0; i < convexHull1.size(); i++) {
//                c1[i] = new double[]{convexHull1.get(i).getLongitude(), convexHull1.get(i).getLatitude()};
//            }
//            double[][] c2 = new double[convexHull2.size()][];
//            for (int i = 0; i < convexHull2.size(); i++) {
//                c2[i] = new double[]{convexHull2.get(i).getLongitude(), convexHull2.get(i).getLatitude()};
//            }
//
//            //对凸包进行格式转换
//            LngAndLat[] newL1 = new LngAndLat[convexHull1.size()];
//            for (int i = 0; i < convexHull1.size(); i++) {
//                newL1[i] = convexHull1.get(i);
//            }
//            LngAndLat[] newL2 = new LngAndLat[convexHull2.size()];
//            for (int i = 0; i < convexHull2.size(); i++) {
//                newL2[i] = convexHull2.get(i);
//            }
//            //对凸包进行排序
//            LngAndLat[] ll1 = LngAndLat.sortPointsByLongitude(newL1);
//            LngAndLat[] ll2 = LngAndLat.sortPointsByLongitude(newL2);
//
//            //获取分割线
//            int i = 0;
//            int j = ll2.length - 1;
//            List<LngAndLat> list = new ArrayList<>();
//            while (i < ll1.length && j >= 0) {
//                LngAndLat left = ll1[i];
//                LngAndLat right = ll2[j];
//                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
//                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
//                LngAndLat middle = new LngAndLat(newLog, newLat);
//                list.add(middle);
//
//                i++;
//                j--;
//            }
//            //对分割线进行纬度的排序
//            LngAndLat[] lines = list.toArray(new LngAndLat[0]);
//            LngAndLat[] r = LngAndLat.sortPointsByLatitude(lines);
//            List<LngAndLat> resultLine = Arrays.stream(r).collect(Collectors.toList());
//            result.add(resultLine);
//            //继续下两个班组
//            head++;
//            tail = (tail + 1) % groups.size();
//        }
//
//        //添加韶关市中心点
//        addCenter(result, SHAOGUAN_CENTER_POINT);
//
//        return result;
//    }

//    @Override
//    public List<List<LngAndLat>> getSplitLines() {
//        List<Group> groups = groupMapper.getGroupsByLikeName();
//
//        if (groups.size() < 2) {
//            throw new IllegalArgumentException("班组数量不够，无法画出分割线！");
//        }
//        //计算班组的多边形，才能按顺序求分割线
//        ArrayList<GroupShapeLngAndLat> groupsArray = new ArrayList<>();
//        ArrayList<GroupShapeLngAndLat> groupsShape = new ArrayList<>();
//        for (Group g : groups) {
//            QueryWrapper<TransitDepot> q = new QueryWrapper<>();
//            q.eq("group_id", g.getGroupId());
//            List<TransitDepot> t = transitDepotMapper.selectList(q);
//            ArrayList<DoublePoint> lngLatMatrix = new ArrayList<>();
//            for (TransitDepot tt : t) {
//                QueryWrapper<Accumulation> aq = new QueryWrapper<>();
//                aq.eq("transit_depot_id", tt.getTransitDepotId()).eq("is_delete", 0);
//                List<Accumulation> accumulations = accumulationMapper.selectList(aq);
//                for (Accumulation a : accumulations) {
//                    lngLatMatrix.add(new DoublePoint(new double[]{a.getLongitude(), a.getLatitude()}));
//                }
//            }
//            List<CentroidCluster<DoublePoint>> centroidClusters = myKmeans(1, 30, 0, lngLatMatrix);
//            double[] center = centroidClusters.get(0).getCenter().getPoint();
//            groupsArray.add(new GroupShapeLngAndLat(new LngAndLat(center[0], center[1]), g.getGroupId()));
//        }
//        LngAndLat[] array = new LngAndLat[groupsArray.size()];
//        for (int i = 0; i < array.length; i++) {
//            array[i] = groupsArray.get(i).getLngAndLat();
//        }
//        List<LngAndLat> cl = ConvexHull.convexHull(array);
//        LngAndLat[] newArray = new LngAndLat[cl.size()];
//        for (int i = 0; i < cl.size(); i++) {
//            newArray[i] = cl.get(i);
//        }
//        for (LngAndLat andLat : array) {
//            if (!cl.contains(andLat)) {
//                newArray = AddPointToConvexHull.addPointToConvexHull(newArray, andLat);
//            }
//        }
//        for (LngAndLat l : array) {
//            int i;
//            for (i = 0; i < groupsArray.size(); i++) {
//                if (groupsArray.get(i).getLngAndLat().equals(l)) {
//                    break;
//                }
//            }
//            groupsShape.add(groupsArray.get(i));
//        }
//
//        //头尾指针
//        int head = 0;
//        int tail = 1;
//
//        List<List<LngAndLat>> result = new ArrayList<>();
//
//        while (head < groupsShape.size()) {
//            //获取两个班组
//            GroupShapeLngAndLat gs1 = groupsShape.get(head);
//            QueryWrapper<Group> gq1 = new QueryWrapper<>();
//            gq1.eq("group_id", gs1.getGroupId());
//            Group g1 = groupMapper.selectOne(gq1);
//
//            GroupShapeLngAndLat gs2 = groupsShape.get(tail);
//            QueryWrapper<Group> gq2 = new QueryWrapper<>();
//            gq2.eq("group_id", gs2.getGroupId());
//            Group g2 = groupMapper.selectOne(gq2);
//
//            //获取两个班组的中转站
//            QueryWrapper<TransitDepot> q1 = new QueryWrapper<>();
//            q1.eq("group_id", g1.getGroupId()).eq("status", 1);
//            List<TransitDepot> d1 = transitDepotMapper.selectList(q1);
//            QueryWrapper<TransitDepot> q2 = new QueryWrapper<>();
//            q2.eq("group_id", g2.getGroupId()).eq("status", 1);
//            List<TransitDepot> d2 = transitDepotMapper.selectList(q2);
//            //检查两个班组是否有中转站
//            if (d1.size() == 0) {
//                head = (head + 1) % groups.size();
//                tail = (tail + 1) % groups.size();
//                groups.remove(g1);
//                continue;
//            }
//            if (d2.size() == 0) {
//                tail = (tail + 1) % groups.size();
//                groups.remove(g2);
//                continue;
//            }
//            //获取两个班组的中转站的聚集区
//            List<Accumulation> a1 = new ArrayList<>();
//            for (TransitDepot d : d1) {
//                QueryWrapper<Accumulation> q3 = new QueryWrapper<>();
//                q3.eq("transit_depot_id", d.getTransitDepotId()).eq("is_delete", 0);
//                List<Accumulation> a = accumulationMapper.selectList(q3);
//                a1.addAll(a);
//            }
//            List<Accumulation> a2 = new ArrayList<>();
//            for (TransitDepot d : d2) {
//                QueryWrapper<Accumulation> q4 = new QueryWrapper<>();
//                q4.eq("transit_depot_id", d.getTransitDepotId()).eq("is_delete", 0);
//                List<Accumulation> a = accumulationMapper.selectList(q4);
//                a2.addAll(a);
//            }
//            //将a1和a2进行格式转换
//            LngAndLat[] ll = new LngAndLat[a1.size() + a2.size()];
//            int k = 0;
//            LngAndLat[] l1 = new LngAndLat[a1.size()];
//            for (int i = 0; i < a1.size(); i++) {
//                l1[i] = new LngAndLat(a1.get(i).getLongitude(), a1.get(i).getLatitude());
//                ll[k] = new LngAndLat(a1.get(i).getLongitude(), a1.get(i).getLatitude());
//                k++;
//            }
//            LngAndLat[] l2 = new LngAndLat[a2.size()];
//            for (int i = 0; i < a2.size(); i++) {
//                l2[i] = new LngAndLat(a2.get(i).getLongitude(), a2.get(i).getLatitude());
//                ll[k] = new LngAndLat(a2.get(i).getLongitude(), a2.get(i).getLatitude());
//                k++;
//            }
//            //获取l1和l2的凸包
//            List<LngAndLat> convexHull1 = ConvexHull.convexHull(l1);
//            List<LngAndLat> convexHull2 = ConvexHull.convexHull(l2);
//            List<LngAndLat> convexHull = ConvexHull.convexHull(ll);
//
//            //剔除外凸包所包含两个凸包的点
//            while (!convexHull.isEmpty()) {
//                LngAndLat lngAndLat = convexHull.get(0);
//                if (convexHull1.contains(lngAndLat)) {
//                    convexHull1.remove(lngAndLat);
//                } else {
//                    convexHull2.remove(lngAndLat);
//                }
//                convexHull.remove(lngAndLat);
//            }
//
//            //对凸包进行格式转换并排序
//            LngAndLat[] newL1 = new LngAndLat[convexHull1.size()];
//            for (int i = 0; i < convexHull1.size(); i++) {
//                newL1[i] = convexHull1.get(i);
//            }
//            LngAndLat[] newL2 = new LngAndLat[convexHull2.size()];
//            for (int i = 0; i < convexHull2.size(); i++) {
//                newL2[i] = convexHull2.get(i);
//            }
//            //对凸包进行排序
//            LngAndLat[] ll1 = LngAndLat.sortPointsByLongitude(newL1);
//            LngAndLat[] ll2 = LngAndLat.sortPointsByLongitude(newL2);
//
//            //获取分割线
//            int i = 0;
//            int j = 0;
//            List<LngAndLat> list = new ArrayList<>();
//            while (i < ll1.length && j < ll2.length) {
//                LngAndLat left = ll1[i];
//                LngAndLat right = ll2[j];
//                if (left.getLongitude() > right.getLongitude() || left.getLatitude() < right.getLatitude()) {
//                    i++;
//                    continue;
//                }
//                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
//                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
//                LngAndLat middle = new LngAndLat(newLog, newLat);
//                list.add(middle);
//
//                i++;
//                j++;
//            }
//            if (i >= ll1.length && ll1.length != 0) {
//                LngAndLat left = ll1[i - 1];
//                while (j < ll2.length) {
//                    LngAndLat right = ll2[j];
//                    double newLog = (left.getLongitude() + right.getLongitude()) / 2;
//                    double newLat = (left.getLatitude() + right.getLatitude()) / 2;
//                    LngAndLat middle = new LngAndLat(newLog, newLat);
//                    list.add(middle);
//                    j++;
//                }
//            }
//            if (j >= ll2.length && ll2.length != 0) {
//                LngAndLat right = ll2[j - 1];
//                while (i < ll1.length) {
//                    LngAndLat left = ll1[i];
//                    double newLog = (left.getLongitude() + right.getLongitude()) / 2;
//                    double newLat = (left.getLatitude() + right.getLatitude()) / 2;
//                    LngAndLat middle = new LngAndLat(newLog, newLat);
//                    list.add(middle);
//                    i++;
//                }
//            }
//            if (ll1.length == 0) {
//
//            }
//            if (ll2.length == 0) {
//
//            }
//            //对分割线进行纬度的排序
//            LngAndLat[] lines = list.toArray(new LngAndLat[0]);
//            LngAndLat[] r = LngAndLat.sortPointsByLatitude(lines);
//            List<LngAndLat> resultLine = Arrays.stream(r).collect(Collectors.toList());
//            result.add(resultLine);
//            //继续下两个班组
//            head++;
//            tail = (tail + 1) % groups.size();
//        }
//
//        //添加中心点
//        double[] center = getCenter();
//        String c = center[0] + "," + center[1];
//        addCenter(result, c);
//
//        return result;
//    }

    @Override
    public List<List<LngAndLat>> getSplitLines(String groupOrder) {
        char[] chars = groupOrder.toCharArray();
        List<Group> groups = new ArrayList<>();
        for (char ch : chars) {
            String name = "班组" + ch;
            groups.add(groupMapper.getGroupsByName(name));
        }

        if (groups.size() < 2) {
            throw new IllegalArgumentException("班组数量不够，无法画出分割线！");
        }

        //头尾指针
        int head = 0;
        int tail = 1;

        List<List<LngAndLat>> result = new ArrayList<>();

        while (head < groups.size()) {
            //获取两个班组
            Group g1 = groups.get(head);
            Group g2 = groups.get(tail);
            //获取两个班组的中转站
            QueryWrapper<TransitDepot> q1 = new QueryWrapper<>();
            q1.eq("group_id", g1.getGroupId()).eq("status", 1);
            List<TransitDepot> d1 = transitDepotMapper.selectList(q1);
            QueryWrapper<TransitDepot> q2 = new QueryWrapper<>();
            q2.eq("group_id", g2.getGroupId()).eq("status", 1);
            List<TransitDepot> d2 = transitDepotMapper.selectList(q2);
            //检查两个班组是否有中转站
            if (d1.size() == 0) {
                head = (head + 1) % groups.size();
                tail = (tail + 1) % groups.size();
                groups.remove(g1);
                continue;
            }
            if (d2.size() == 0) {
                tail = (tail + 1) % groups.size();
                groups.remove(g2);
                continue;
            }
            //获取两个班组的中转站的聚集区
            List<Accumulation> a1 = new ArrayList<>();
            for (TransitDepot d : d1) {
                QueryWrapper<Accumulation> q3 = new QueryWrapper<>();
                q3.eq("transit_depot_id", d.getTransitDepotId()).eq("is_delete", 0);
                List<Accumulation> a = accumulationMapper.selectList(q3);
                a1.addAll(a);
            }
            List<Accumulation> a2 = new ArrayList<>();
            for (TransitDepot d : d2) {
                QueryWrapper<Accumulation> q4 = new QueryWrapper<>();
                q4.eq("transit_depot_id", d.getTransitDepotId()).eq("is_delete", 0);
                List<Accumulation> a = accumulationMapper.selectList(q4);
                a2.addAll(a);
            }
            //将a1和a2进行格式转换
            LngAndLat[] ll = new LngAndLat[a1.size() + a2.size()];
            int k = 0;
            LngAndLat[] l1 = new LngAndLat[a1.size()];
            for (int i = 0; i < a1.size(); i++) {
                l1[i] = new LngAndLat(a1.get(i).getLongitude(), a1.get(i).getLatitude());
                ll[k] = new LngAndLat(a1.get(i).getLongitude(), a1.get(i).getLatitude());
                k++;
            }
            LngAndLat[] l2 = new LngAndLat[a2.size()];
            for (int i = 0; i < a2.size(); i++) {
                l2[i] = new LngAndLat(a2.get(i).getLongitude(), a2.get(i).getLatitude());
                ll[k] = new LngAndLat(a2.get(i).getLongitude(), a2.get(i).getLatitude());
                k++;
            }
            //获取l1和l2的凸包
            List<LngAndLat> convexHull1 = ConvexHull.convexHull(l1);
            List<LngAndLat> convexHull2 = ConvexHull.convexHull(l2);
            List<LngAndLat> convexHull = ConvexHull.convexHull(ll);

            //剔除外凸包所包含两个凸包的点
            while (!convexHull.isEmpty()) {
                LngAndLat lngAndLat = convexHull.get(0);
                if (convexHull1.contains(lngAndLat)) {
                    convexHull1.remove(lngAndLat);
                } else {
                    convexHull2.remove(lngAndLat);
                }
                convexHull.remove(lngAndLat);
            }

            //对凸包进行格式转换并排序
            LngAndLat[] newL1 = new LngAndLat[convexHull1.size()];
            for (int i = 0; i < convexHull1.size(); i++) {
                newL1[i] = convexHull1.get(i);
            }
            LngAndLat[] newL2 = new LngAndLat[convexHull2.size()];
            for (int i = 0; i < convexHull2.size(); i++) {
                newL2[i] = convexHull2.get(i);
            }
            //对凸包进行排序
            LngAndLat[] ll1 = sortConvexHull(newL1);
            LngAndLat[] ll2 = sortConvexHull(newL2);
            //获取分割线
            int i = 0;
            int j = 0;
            List<LngAndLat> list = new ArrayList<>();
            while (i < ll1.length && j < ll2.length) {
                LngAndLat left = ll1[i];
                LngAndLat right = ll2[j];
//                if (left.getLongitude() > right.getLongitude() || left.getLatitude() < right.getLatitude()) {
//                    i++;
//                    continue;
//                }
                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
                LngAndLat middle = new LngAndLat(newLog, newLat);
                list.add(middle);

                i++;
                j++;
            }
            if (i >= ll1.length && ll1.length != 0) {
                LngAndLat left = ll1[i - 1];
                while (j < ll2.length) {
                    LngAndLat right = ll2[j];
                    double newLog = (left.getLongitude() + right.getLongitude()) / 2;
                    double newLat = (left.getLatitude() + right.getLatitude()) / 2;
                    LngAndLat middle = new LngAndLat(newLog, newLat);
                    list.add(middle);
                    j++;
                }
            }
            if (j >= ll2.length && ll2.length != 0) {
                LngAndLat right = ll2[j - 1];
                while (i < ll1.length) {
                    LngAndLat left = ll1[i];
                    double newLog = (left.getLongitude() + right.getLongitude()) / 2;
                    double newLat = (left.getLatitude() + right.getLatitude()) / 2;
                    LngAndLat middle = new LngAndLat(newLog, newLat);
                    list.add(middle);
                    i++;
                }
            }
            if (ll1.length == 0 || ll2.length == 0) {
                convexHull1 = ConvexHull.convexHull(l1);
                convexHull2 = ConvexHull.convexHull(l2);
                newL1 = new LngAndLat[convexHull1.size()];
                for (int a = 0; a < convexHull1.size(); a++) {
                    newL1[a] = convexHull1.get(a);
                }
                newL2 = new LngAndLat[convexHull2.size()];
                for (int b = 0; b < convexHull2.size(); b++) {
                    newL2[b] = convexHull2.get(b);
                }
                ll1 = sortConvexHull(newL1);
                ll2 = sortConvexHull(newL2);
                while (i < ll1.length && j < ll2.length) {
                    LngAndLat left = ll1[i];
                    LngAndLat right = ll2[j];
                    double newLog = (left.getLongitude() + right.getLongitude()) / 2;
                    double newLat = (left.getLatitude() + right.getLatitude()) / 2;
                    LngAndLat middle = new LngAndLat(newLog, newLat);
                    list.add(middle);
                    i++;
                    j++;
                }
            }
            //对分割线进行纬度的排序
            LngAndLat[] lines = list.toArray(new LngAndLat[0]);
            LngAndLat[] r = LngAndLat.sortPointsByLatitude(lines);
            List<LngAndLat> resultLine = Arrays.stream(r).collect(Collectors.toList());
            result.add(resultLine);
            //继续下两个班组
            head++;
            tail = (tail + 1) % groups.size();
        }

        //添加中心点
        double[] center = getCenter();
        String c = center[0] + "," + center[1];
        addCenter(result, c);

        //添加边界点
        addBoundary(result, new LngAndLat(center[0], center[1]));

        return result;
    }

    @Override
    public List<List<LngAndLat>> getColourConvexHull(GetColourConvexHullFrom requestParam) {
        //检查group是否存在
        Group group = groupMapper.getGroupsByName(requestParam.getGroupName());
        if (group == null) {
            throw new IllegalArgumentException("班组不存在");
        }

        //边界点集合
        List<LngAndLat> boundary = new ArrayList<>();
        //获取韶关市边界点并放入boundary集合中
        String[] splits = getShaoguanBoundary().split(";");
        for (String s : splits) {
            String[] doubles = s.split(",");
            boundary.add(new LngAndLat(Double.parseDouble(doubles[0]), Double.parseDouble(doubles[1])));
        }
        //将班组分割线放入boundary集合中
        List<double[]> splitLines = requestParam.getSplitLines();
        for (double[] d : splitLines) {
            boundary.add(new LngAndLat(d[0], d[1]));
        }

        //凸包扩大后实际发生改变的凸包集合
        List<List<LngAndLat>> affectedConvexHull = new ArrayList<>();
        //凸包扩大后实际未发生改变的凸包集合
        List<List<LngAndLat>> unaffectedConvexHull = new ArrayList<>();

        //该班组的所有凸包
        List<List<LngAndLat>> groupConvexHulls = new ArrayList<>();
        QueryWrapper<TransitDepot> q1 = new QueryWrapper<>();
        q1.eq("group_id", group.getGroupId()).eq("status", 1);
        List<TransitDepot> transitDepots = transitDepotMapper.selectList(q1);
        for (TransitDepot t : transitDepots) {
            QueryWrapper<Route> q2 = new QueryWrapper<>();
            q2.eq("transit_depot_id", t.getTransitDepotId()).eq("is_delete", 0);
            List<Route> routes = routeMapper.selectList(q2);
            for (Route r : routes) {
                List<LngAndLat> list = new ArrayList<>();
                String convex = r.getConvex();
                String[] split = convex.split(";");
                for (String s : split) {
                    String[] lngLat = s.split(",");
                    list.add(new LngAndLat(Double.parseDouble(lngLat[0]), Double.parseDouble(lngLat[1])));
                }
                groupConvexHulls.add(list);
            }
        }
        //获取该班组的中心点
        ArrayList<DoublePoint> groupConvexHullsArray = new ArrayList<>();
        for (List<LngAndLat> ll : groupConvexHulls) {
            for (LngAndLat l : ll) {
                groupConvexHullsArray.add(new DoublePoint(new double[]{l.getLongitude(), l.getLatitude()}));
            }
        }
        List<CentroidCluster<DoublePoint>> centroidClusters = myKmeans(1, 30, 0, groupConvexHullsArray);
        double[] center = centroidClusters.get(0).getCenter().getPoint();

        recursion(boundary, groupConvexHulls, unaffectedConvexHull, affectedConvexHull, new LngAndLat(center[0], center[1]));

        return affectedConvexHull;
    }

    @Override
    public List<ConvexPointVO> getConvexPoint() {
        QueryWrapper<Route> queryWrapper = new QueryWrapper<>();
        queryWrapper.eq("is_delete", 0);
        List<Route> routes = routeMapper.selectList(queryWrapper);

        List<ConvexPointVO> result = new ArrayList<>();
        for (Route route : routes) {
            String convex = route.getConvex();
            String[] splits = convex.split(";");
            for (String s : splits) {
                String[] lngandlat = s.split(",");
                QueryWrapper<Accumulation> accumulationQueryWrapper = new QueryWrapper<>();
                accumulationQueryWrapper.eq("is_delete", 0).eq("longitude", lngandlat[0]).eq("latitude", lngandlat[1]);
                Accumulation accumulation = accumulationMapper.selectOne(accumulationQueryWrapper);
                ConvexPointVO convexPointVO = new ConvexPointVO();
                convexPointVO.setLongitude(accumulation.getLongitude());
                convexPointVO.setLatitude(accumulation.getLatitude());
                convexPointVO.setAccumulationId(accumulation.getAccumulationId());
                convexPointVO.setRouteName(route.getRouteName());
                result.add(convexPointVO);
            }
        }
        return result;
    }

    private void recursion(List<LngAndLat> boundary, List<List<LngAndLat>> groupConvexHulls, List<List<LngAndLat>> unaffectedConvexHull, List<List<LngAndLat>> affectedConvexHull, LngAndLat center) {
        //递归推出条件
        if (groupConvexHulls.size() == 0) {
            return;
        }

        //1.对还有的所有路线凸包进行凸包运算
        int size = 0;
        for (List<LngAndLat> l : groupConvexHulls) {
            size += l.size();
        }
        LngAndLat[] gch = new LngAndLat[size];
        int k = 0;
        for (List<LngAndLat> l : groupConvexHulls) {
            for (LngAndLat ll : l) {
                gch[k] = ll;
                k++;
            }
        }
        List<LngAndLat> convexHull = ConvexHull.convexHull(removeDuplicates(gch));

        //2.根据convexHull找到对应所在的凸包，在groupConvexHulls中删除，并添加到unaffectedConvexHull中
        for (LngAndLat l : convexHull) {
            for (List<LngAndLat> ll : groupConvexHulls) {
                if (ll.contains(l) && !unaffectedConvexHull.contains(ll)) {
                    unaffectedConvexHull.add(ll);
                    break;
                }
            }
        }
        for (List<LngAndLat> ll : unaffectedConvexHull) {
            groupConvexHulls.remove(ll);
        }

        //头尾指针
        int head = 0;
        int tail = 1;

        int aSize = affectedConvexHull.size();
        //对外层一圈的凸包进行处理
        while (head < unaffectedConvexHull.size()) {
            //如果affectedConvexHull的对应索引处没有元素，那么就表明这个凸包还没有扩大化
            if (head + aSize >= affectedConvexHull.size()) {
                List<LngAndLat> enlarge = enlarge(unaffectedConvexHull.get(head));
                //将原来的凸包修改扩大化后的凸包
                unaffectedConvexHull.remove(head);
                unaffectedConvexHull.add(head, enlarge);
                //添加到affectedConvexHull中
                affectedConvexHull.add(head + aSize, enlarge);
            }
            //tail所指向的凸包同理
            if (tail + aSize >= affectedConvexHull.size()) {
                List<LngAndLat> enlarge = enlarge(unaffectedConvexHull.get(tail));
                //将原来的凸包修改扩大化后的凸包
                unaffectedConvexHull.remove(tail);
                unaffectedConvexHull.add(tail, enlarge);
                //添加到affectedConvexHull中
                affectedConvexHull.add(tail + aSize, enlarge);
            }
            //3.获取扩大后的这两个凸包
            List<LngAndLat> l1 = affectedConvexHull.get(head + aSize);
            List<LngAndLat> l2 = affectedConvexHull.get(tail + aSize);
            //进行这两个小凸包的复制，防止后面的remove操作影响到这两个小凸包
            List<LngAndLat> l1andl2 = new ArrayList<>();
            List<LngAndLat> l1copy = new ArrayList<>();
            for (LngAndLat l : l1) {
                l1copy.add(l);
                l1andl2.add(l);
            }
            List<LngAndLat> l2copy = new ArrayList<>();
            for (LngAndLat l : l2) {
                l2copy.add(l);
                l1andl2.add(l);
            }
            LngAndLat[] l = new LngAndLat[l1andl2.size()];
            for (int i = 0; i < l1andl2.size(); i++) {
                l[i] = l1andl2.get(i);
            }
            List<LngAndLat> convex = ConvexHull.convexHull(removeDuplicates(l));
            List<LngAndLat> convexCopy = new ArrayList<>(convex);
            //获取这两个凸包的分割线
            List<LngAndLat> lines = getLines(l1copy, l2copy, convexCopy);
            //4.将分割线和凸包进行整合，达到两个凸包有重合边的效果
            List<LngAndLat> al1 = affectedConvexHull.get(head + aSize);
            List<LngAndLat> al2 = affectedConvexHull.get(tail + aSize);
            al1.removeIf(lngAndLat -> !convex.contains(lngAndLat));
            al2.removeIf(lngAndLat -> !convex.contains(lngAndLat));
            al1.addAll(lines);
            List<LngAndLat> filteredSplitLines = new ArrayList<>();
            LngAndLat[] al1Con = new LngAndLat[al1.size()];
            for (int i = 0; i < al1Con.length; i++) {
                al1Con[i] = al1.get(i);
            }
            List<LngAndLat> newAffectedConvexHull1 = ConvexHull.convexHull(removeDuplicates(al1Con));
            for (LngAndLat lngAndLat : newAffectedConvexHull1) {
                if (lines.contains(lngAndLat)) {
                    al2.add(lngAndLat);
                    filteredSplitLines.add(lngAndLat);
                }
            }
            LngAndLat[] al2Con = new LngAndLat[al2.size()];
            for (int i = 0; i < al2Con.length; i++) {
                al2Con[i] = al2.get(i);
            }
            List<LngAndLat> newAffectedConvexHull2 = ConvexHull.convexHull(removeDuplicates(al2Con));
            newAffectedConvexHull1.add(newAffectedConvexHull1.get(0));
            newAffectedConvexHull2.add(newAffectedConvexHull2.get(0));
            //将affectedConvexHull中head和tail对应的原来的两个扩大化凸包，替换为这两个整合之后的凸包
            affectedConvexHull.remove(head + aSize);
            affectedConvexHull.add(head + aSize, newAffectedConvexHull1);
            affectedConvexHull.remove(tail + aSize);
            affectedConvexHull.add(tail + aSize, newAffectedConvexHull2);
            //看分割线中的第一个点还是最后一个点离边界更近，获得更近的那个点所连接的边界点
//            LngAndLat nearestPoint = FindNearestBoundaryPoint.find(lines.get(0), lines.get(lines.size() - 1), boundary, center);
            ArrayList<LngAndLat> list = FindNearestBoundaryPoint.find(filteredSplitLines, boundary, center);
            //5.将nearestPoint加入到affectedConvexHull的两个凸包中
//            affectedConvexHull.get(head + aSize).add(nearestPoint);
//            affectedConvexHull.get(tail + aSize).add(nearestPoint);
            List<LngAndLat> list1 = addNearestPoint(affectedConvexHull.get(head + aSize), list, filteredSplitLines);
            if (list1 != null) {
                affectedConvexHull.remove(head + aSize);
                affectedConvexHull.add(head + aSize, list1);
            }
            List<LngAndLat> list2 = addNearestPoint(affectedConvexHull.get(tail + aSize), list, filteredSplitLines);
            if (list2 != null) {
                affectedConvexHull.remove(tail + aSize);
                affectedConvexHull.add(tail + aSize, list2);
            }

            head++;
            tail = (tail + 1) % unaffectedConvexHull.size();
        }

        //最后对affectedConvexHull里的每一个元素进行凸包计算，以再扩大一次
//        for (int i = aSize; i < affectedConvexHull.size(); i++) {
//            List<LngAndLat> convex = affectedConvexHull.get(i);
//            LngAndLat[] list = new LngAndLat[convex.size()];
//            int j = 0;
//            for (LngAndLat l : convex) {
//                list[j] = l;
//                j++;
//            }
//            List<LngAndLat> newConvex = ConvexHull.convexHull(list);
//            affectedConvexHull.remove(i);
//            affectedConvexHull.add(i, newConvex);
//        }

        //更新边界点
        boundary.clear();
        for (List<LngAndLat> ll : affectedConvexHull) {
            boundary.addAll(ll);
        }
        //清空unaffectedConvexHull
        unaffectedConvexHull.clear();

        recursion(boundary, groupConvexHulls, unaffectedConvexHull, affectedConvexHull, center);
    }

    /**
     * 将nearestPoint加入到affectedConvexHull的两个凸包中
     *
     * @param convexHull         待加入到的凸包
     * @param list               离边界点最近的点和加入元素
     * @param filteredSplitLines 过滤后的分割线
     * @return 修改之后的convexHull
     */
    private List<LngAndLat> addNearestPoint(List<LngAndLat> convexHull, ArrayList<LngAndLat> list, List<LngAndLat> filteredSplitLines) {
        //离边界点最近的点
        LngAndLat linesPoint = list.get(0);
        //加入元素
        LngAndLat nearestPoint = list.get(1);

        int idx = convexHull.indexOf(linesPoint);
        if (idx == 0) {
            convexHull.add(0, nearestPoint);
        } else if (idx == convexHull.size() - 1) {
            convexHull.add(nearestPoint);
        } else {
            //看是添加在convexHull的idx索引处的左侧还是右侧
            if (filteredSplitLines.contains(convexHull.get(idx + 1))) {
                //加在左侧
                convexHull.add(idx, nearestPoint);
            } else if (filteredSplitLines.contains(convexHull.get(idx - 1))) {
                //加在右侧
                convexHull.add(idx + 1, nearestPoint);
            } else {
                //filteredSplitLines只存在一个元素，不好判断是加在左侧还是右侧，直接进行凸包处理
                LngAndLat[] a = new LngAndLat[convexHull.size() + 1];
                for (int i = 0; i < convexHull.size(); i++) {
                    a[i] = convexHull.get(i);
                }
                a[a.length - 1] = nearestPoint;
                List<LngAndLat> c = ConvexHull.convexHull(removeDuplicates(a));
                c.add(c.get(0));
                return c;
            }
        }
        return null;
    }

    /**
     * 数组去重
     *
     * @param array 带去重数组
     * @return 去重后数组
     */
    private static LngAndLat[] removeDuplicates(LngAndLat[] array) {
        // 使用LinkedHashSet保持元素的插入顺序
        Set<LngAndLat> set = new LinkedHashSet<>(Arrays.asList(array));
        LngAndLat[] uniqueArray = new LngAndLat[set.size()];
        int index = 0;
        for (LngAndLat s : set) {
            uniqueArray[index++] = s;
        }
        return uniqueArray;
    }

    /**
     * 获取两个小凸包的分割线
     *
     * @param convexHull1 凸包一
     * @param convexHull2 凸包二
     * @param convexHull  两个凸包的外层凸包
     * @return 两个小凸包的分割线
     */
    private List<LngAndLat> getLines1(List<LngAndLat> convexHull1, List<LngAndLat> convexHull2, List<LngAndLat> convexHull) {
        //剔除外凸包所包含两个凸包的点
        while (!convexHull.isEmpty()) {
            LngAndLat lngAndLat = convexHull.get(0);
            if (convexHull1.contains(lngAndLat)) {
                convexHull1.remove(lngAndLat);
            } else {
                convexHull2.remove(lngAndLat);
            }
            convexHull.remove(lngAndLat);
        }

        //对凸包进行格式转换
        LngAndLat[] newL1 = new LngAndLat[convexHull1.size()];
        for (int i = 0; i < convexHull1.size(); i++) {
            newL1[i] = convexHull1.get(i);
        }
        LngAndLat[] newL2 = new LngAndLat[convexHull2.size()];
        for (int i = 0; i < convexHull2.size(); i++) {
            newL2[i] = convexHull2.get(i);
        }
        //对凸包进行排序
        LngAndLat[] ll1 = sortConvexHull(newL1);
        LngAndLat[] ll2 = sortConvexHull(newL2);
        //获取分割线
        int i = 0;
        int j = 0;
        List<LngAndLat> list = new ArrayList<>();
        while (i < ll1.length && j < ll2.length) {
            LngAndLat left = ll1[i];
            LngAndLat right = ll2[j];
            double newLog = (left.getLongitude() + right.getLongitude()) / 2;
            double newLat = (left.getLatitude() + right.getLatitude()) / 2;
            LngAndLat middle = new LngAndLat(newLog, newLat);
            list.add(middle);

            i++;
            j++;
        }
        if (i >= ll1.length && ll1.length != 0) {
            LngAndLat left = ll1[i - 1];
            while (j < ll2.length) {
                LngAndLat right = ll2[j];
                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
                LngAndLat middle = new LngAndLat(newLog, newLat);
                list.add(middle);
                j++;
            }
        }
        if (j >= ll2.length && ll2.length != 0) {
            LngAndLat right = ll2[j - 1];
            while (i < ll1.length) {
                LngAndLat left = ll1[i];
                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
                LngAndLat middle = new LngAndLat(newLog, newLat);
                list.add(middle);
                i++;
            }
        }
        if (ll1.length == 0 || ll2.length == 0) {
            newL1 = new LngAndLat[convexHull1.size()];
            for (int a = 0; a < convexHull1.size(); a++) {
                newL1[a] = convexHull1.get(a);
            }
            newL2 = new LngAndLat[convexHull2.size()];
            for (int b = 0; b < convexHull2.size(); b++) {
                newL2[b] = convexHull2.get(b);
            }
            ll1 = sortConvexHull(newL1);
            ll2 = sortConvexHull(newL2);
            while (i < ll1.length && j < ll2.length) {
                LngAndLat left = ll1[i];
                LngAndLat right = ll2[j];
                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
                LngAndLat middle = new LngAndLat(newLog, newLat);
                list.add(middle);
                i++;
                j++;
            }
        }

        return list;
    }

    private List<LngAndLat> getLines(List<LngAndLat> convexHull1, List<LngAndLat> convexHull2, List<LngAndLat> convexHull) {
        //剔除外凸包所包含两个凸包的点
        while (!convexHull.isEmpty()) {
            LngAndLat lngAndLat = convexHull.get(0);
            if (convexHull1.contains(lngAndLat)) {
                convexHull1.remove(lngAndLat);
            } else {
                convexHull2.remove(lngAndLat);
            }
            convexHull.remove(lngAndLat);
        }

        //对凸包进行格式转换
        LngAndLat[] newL1 = new LngAndLat[convexHull1.size()];
        for (int i = 0; i < convexHull1.size(); i++) {
            newL1[i] = convexHull1.get(i);
        }
        LngAndLat[] newL2 = new LngAndLat[convexHull2.size()];
        for (int i = 0; i < convexHull2.size(); i++) {
            newL2[i] = convexHull2.get(i);
        }
        //对凸包进行排序
        LngAndLat[] ll1 = sortConvexHull(newL1);
        LngAndLat[] ll2 = sortConvexHull(newL2);
        //获取分割线
        int i = 0;
        int j = 0;
        List<LngAndLat> list = new ArrayList<>();
        //将i或j往后移n个位置，为了从更近的点开始求分割线
        double v2 = Double.MAX_VALUE;
        LngAndLat l1 = ll1[i];
        int minJ = 0;
        for (int k = 0; k < ll2.length; k++) {
            LngAndLat l2 = ll2[k];
            double v = calculateEuclideanDistance(new double[]{l1.getLongitude(), l1.getLatitude()}, new double[]{l2.getLongitude(), l2.getLatitude()});
            if (v < v2) {
                v2 = v;
                minJ = k;
            }
        }
        double v1 = Double.MAX_VALUE;
        LngAndLat l2 = ll2[j];
        int minI = 0;
        for (int k = 0; k < ll1.length; k++) {
            LngAndLat l = ll1[k];
            double v = calculateEuclideanDistance(new double[]{l2.getLongitude(), l2.getLatitude()}, new double[]{l.getLongitude(), l.getLatitude()});
            if (v < v1) {
                v1 = v;
                minI = k;
            }
        }
        if (v2 < v1) {
            j = minJ;
        } else {
            i = minI;
        }
        while (i < ll1.length && j < ll2.length) {
            LngAndLat left = ll1[i];
            LngAndLat right = ll2[j];
            double newLog = (left.getLongitude() + right.getLongitude()) / 2;
            double newLat = (left.getLatitude() + right.getLatitude()) / 2;
            LngAndLat middle = new LngAndLat(newLog, newLat);
            list.add(middle);

            i++;
            j++;
        }
//        if (i >= ll1.length && ll1.length != 0) {
//            LngAndLat left = ll1[i - 1];
//            while (j < ll2.length) {
//                LngAndLat right = ll2[j];
//                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
//                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
//                LngAndLat middle = new LngAndLat(newLog, newLat);
//                list.add(middle);
//                j++;
//            }
//        }
//        if (j >= ll2.length && ll2.length != 0) {
//            LngAndLat right = ll2[j - 1];
//            while (i < ll1.length) {
//                LngAndLat left = ll1[i];
//                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
//                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
//                LngAndLat middle = new LngAndLat(newLog, newLat);
//                list.add(middle);
//                i++;
//            }
//        }
        if (ll1.length == 0 || ll2.length == 0) {
            newL1 = new LngAndLat[convexHull1.size()];
            for (int a = 0; a < convexHull1.size(); a++) {
                newL1[a] = convexHull1.get(a);
            }
            newL2 = new LngAndLat[convexHull2.size()];
            for (int b = 0; b < convexHull2.size(); b++) {
                newL2[b] = convexHull2.get(b);
            }
            ll1 = sortConvexHull(newL1);
            ll2 = sortConvexHull(newL2);
            while (i < ll1.length && j < ll2.length) {
                LngAndLat left = ll1[i];
                LngAndLat right = ll2[j];
                double newLog = (left.getLongitude() + right.getLongitude()) / 2;
                double newLat = (left.getLatitude() + right.getLatitude()) / 2;
                LngAndLat middle = new LngAndLat(newLog, newLat);
                list.add(middle);
                i++;
                j++;
            }
        }

        return list;
    }

    /**
     * 凸包扩大化
     *
     * @param list 凸包
     */
    private List<LngAndLat> enlarge(List<LngAndLat> list) {
        //获取这个凸包的中心点（也可以用myKmeans），以用于后续计算
        double newLog = 0;
        double newLat = 0;
        for (LngAndLat l : list) {
            newLog += l.getLongitude();
            newLat += l.getLatitude();
        }
        newLog /= list.size();
        newLat /= list.size();
        double[] center = new double[]{newLog, newLat};

        List<LngAndLat> result = new ArrayList<>();
        //头尾指针
        int head = 0;
        int tail = 1;
        while (head < list.size()) {
            //获取凸包的两个点
            LngAndLat p1 = list.get(head);
            LngAndLat p2 = list.get(tail);
            //创建以这两个点为顶点的正方形的另外两个顶点
            LngAndLat p3 = new LngAndLat(p1.getLongitude(), p2.getLatitude());
            LngAndLat p4 = new LngAndLat(p2.getLongitude(), p1.getLatitude());
            //计算哪个点距离中心点更远
            double v1 = calculateEuclideanDistance(new double[]{p3.getLongitude(), p3.getLatitude()}, center);
            double v2 = calculateEuclideanDistance(new double[]{p4.getLongitude(), p4.getLatitude()}, center);
            if (v1 > v2) {
                result.add(p3);
            } else {
                result.add(p4);
            }

            head++;
            tail = (tail + 1) % list.size();
        }

        return result;
    }

    /**
     * 决定凸包这部分点是按经度排序还是按纬度排序
     *
     * @param newL 凸包部分点
     * @return 排序后的凸包部分点
     */
    private LngAndLat[] sortConvexHull(LngAndLat[] newL) {
        double newLogAbs = 0;
        double newLatAbs = 0;
        for (int i = 0; i < newL.length - 1; i++) {
            newLogAbs += Math.abs(newL[i].getLongitude() - newL[i + 1].getLongitude());
            newLatAbs += Math.abs(newL[i].getLatitude() - newL[i + 1].getLatitude());
        }
        LngAndLat[] ll = null;
        if (newLogAbs > newLatAbs) {
            ll = LngAndLat.sortPointsByLongitude(newL);
        } else {
            ll = LngAndLat.sortPointsByLatitude(newL);
        }
        return ll;
    }

    /**
     * 计算所有聚集区聚集起来的中心点
     */
    private double[] getCenter() {
        List<Accumulation> accumulations = accumulationMapper.selectList(null);
        ArrayList<DoublePoint> lngLatMatrix = new ArrayList<>();
        for (Accumulation a : accumulations) {
            lngLatMatrix.add(new DoublePoint(new double[]{a.getLongitude(), a.getLatitude()}));
        }
        List<CentroidCluster<DoublePoint>> centroidClusters = myKmeans(1, 30, 0, lngLatMatrix);
        return centroidClusters.get(0).getCenter().getPoint();
    }

    /**
     * 添加区域中心点到每一个分割线数组
     *
     * @param list                分割线数组集合
     * @param shaoguanCenterPoint 所选择的区域中心
     */
    private void addCenter1(List<List<LngAndLat>> list, String shaoguanCenterPoint) {
        String[] split = shaoguanCenterPoint.split(",");
        LngAndLat center = new LngAndLat(Double.parseDouble(split[0]), Double.parseDouble(split[1]));
        for (List<LngAndLat> l : list) {
            l.add(0, center);
        }
    }

    private void addCenter(List<List<LngAndLat>> list, String shaoguanCenterPoint) {
        String[] split = shaoguanCenterPoint.split(",");
        LngAndLat center = new LngAndLat(Double.parseDouble(split[0]), Double.parseDouble(split[1]));
        double[] centerDoubles = {center.getLongitude(), center.getLatitude()};
        for (List<LngAndLat> l : list) {
            double min = Double.MAX_VALUE;
            int minIndex = -1;
            for (int i = 0; i < l.size(); i++) {
                double[] doubles = {l.get(i).getLongitude(), l.get(i).getLatitude()};
                double v = calculateEuclideanDistance(centerDoubles, doubles);
                if (v < min) {
                    min = v;
                    minIndex = i;
                }
            }
            //插入center
            if (minIndex == 0) {
                l.add(0, center);
            } else if (minIndex == l.size() - 1) {
                l.add(l.size(), center);
            } else {
                int m = (l.size() - 1) >>> 1;
                //删除后半部分 (l.size() % 2 != 0是照着地图写出来的了，先射箭后画靶了)
                if (minIndex >= m && l.size() % 2 != 0) {
                    l.add(minIndex + 1, center);
                    int size = l.size();
                    if (size > minIndex + 1 + 1) {
                        l.subList(minIndex + 1 + 1, size).clear();
                    }
                    //删除前半部分
                } else {
                    for (int i = 0; i <= minIndex; i++) {
                        l.remove(0);
                    }
                    l.add(0, center);
                }
            }
        }
    }

    /**
     * 将离点最近的边界点加入到List里
     *
     * @param list 分割线数组集合
     */
    private void addBoundary1(List<List<LngAndLat>> list) {
        String[] splits = getShaoguanBoundary().split(";");
        for (List<LngAndLat> l : list) {
            double min = Double.MAX_VALUE;
            double[] added = null;
            double[] p1 = new double[]{l.get(0).getLongitude(), l.get(0).getLatitude()};
            for (String s : splits) {
                String[] doubles = s.split(",");
                double[] p2 = new double[]{Double.parseDouble(doubles[0]), Double.parseDouble(doubles[1])};
                //找出距离最小的边界点
                double dist = calculateEuclideanDistance(p1, p2);
                if (dist < min) {
                    min = dist;
                    added = p2;
                }
            }
            if (added != null) {
                l.add(new LngAndLat(added[0], added[1]));
            }
        }
    }

    private void addBoundary(List<List<LngAndLat>> list, LngAndLat center) {
        String[] splits = getShaoguanBoundary().split(";");
        for (List<LngAndLat> l : list) {
            double[] p1 = null;
            int p1Index = -1;
            if (l.get(0).equals(center)) {
                p1Index = l.size() - 1;
            } else {
                p1Index = 0;
            }
            p1 = new double[]{l.get(p1Index).getLongitude(), l.get(p1Index).getLatitude()};
            double min = Double.MAX_VALUE;
            double[] added = null;
            for (String s : splits) {
                String[] doubles = s.split(",");
                double[] p2 = new double[]{Double.parseDouble(doubles[0]), Double.parseDouble(doubles[1])};
                //找出距离最小的边界点
                double dist = calculateEuclideanDistance(p1, p2);
                if (dist < min) {
                    min = dist;
                    added = p2;
                }
            }
            if (added != null && p1Index == 0) {
                l.add(0, new LngAndLat(added[0], added[1]));
            } else if (added != null && p1Index == l.size() - 1) {
                l.add(l.size(), new LngAndLat(added[0], added[1]));
            }
        }
    }

    /**
     * 两点之间欧氏距离的计算方法
     */
    private double calculateEuclideanDistance(double[] point1, double[] point2) {
        double sum = 0.0;
        for (int i = 0; i < point1.length; i++) {
            sum += Math.pow(point1[i] - point2[i], 2);
        }
        return Math.sqrt(sum);
    }

    private List<CentroidCluster<DoublePoint>> myKmeans(int bestK, int maxIterations, int randomSeed, ArrayList<
            DoublePoint> lngLatMatrix) {
        RandomGenerator randomGenerator = new MersenneTwister(randomSeed);
        //使用k-means聚类算法进行分类，聚类的簇数为best_k
        KMeansPlusPlusClusterer<DoublePoint> bestClusterer = new KMeansPlusPlusClusterer<>(bestK, maxIterations, new EuclideanDistance(), randomGenerator);
        return bestClusterer.cluster(lngLatMatrix);
    }
}
